package com.xiongtian.huffmanTree;

import com.sun.xml.internal.ws.api.model.wsdl.WSDLOutput;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author xiongtian
 * @version 1.0
 * @date 2021/4/22 19:46
 */
public class HuffmanTree {
    public static void main(String[] args) {

        int arr[] = {13, 7, 8, 3, 29, 6, 1};

        Node root = createHuffmanTree(arr);
        // 测试
        preOrder(root);
    }

    public static void preOrder(Node root) {
        if (root == null) {
            System.out.println("该赫夫曼树是一棵空树！");
            return;
        }
        root.preOrder();
    }

    // 创建赫夫曼树的方法
    /**
     *
     * @param arr 需要创建成赫夫曼树的数组
     * @return 创建好后的赫夫曼树
     */
    public static Node createHuffmanTree(int[] arr) {
        // 第一步：为了操作方便
        // 1. 遍历arr数组
        // 2. 将arr的每个元素构建成一个node，
        // 3. 将node放入到ArrayList中
        List<Node> nodes = new ArrayList<>();
        for (int val : arr) {
            nodes.add(new Node(val));
        }

        // 我们处理的过程是个循环过程
        while (nodes.size() > 1) {
            // 从小到大排序
            Collections.sort(nodes);
            System.out.println("nodes:" + nodes);

            // 取出根节点权值最小的两棵二叉树
            // (1) 取出权值最小的节点（二叉树）
            Node leftNode = nodes.get(0);
            // (2) 取出权值第二小的节点(二叉树)
            Node rightNode = nodes.get(1);

            // (3) 构建一棵新的二叉树
            Node parent = new Node(leftNode.val + rightNode.val);
            parent.left = leftNode;
            parent.right = rightNode;

            // (4) 从ArrayList中删除处理过得二叉树
            nodes.remove(leftNode);
            nodes.remove(rightNode);

            // (5) 将parent加入
            nodes.add(parent);
            //System.out.println("第一次处理后：" + nodes);
        }
        // 返回赫夫曼树的root节点
        return nodes.get(0);
    }
}

// 创建节点类
// 为了让Node 对象支持排序Collections集合排序
// 让Node实现Comparable
class Node implements Comparable<Node> {

    int val; // 节点的权值
    Node left;// 指向左子节点
    Node right;// 指向右子节点


    public Node(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        // this.val - o.val : 表示从下到大排
        // -(this.val - o.val) : 表示从大到小排
        return this.val - o.val;
    }

    // 写一个前序遍历
    public void preOrder() {
        System.out.printf("%d ",this.val);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }
}